package com.gxc.tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定两个整数数组 preorder 和 inorder ，
 * 其中 preorder 是二叉树的先序遍历，
 * inorder 是同一棵树的中序遍历，
 * 请构造二叉树并返回其根节点。
 */
public class BuildTree {

    public static void main(String[] args) {
        buildTree2(new int[]{3, 9, 8, 5, 4, 10, 20, 15, 7}, new int[]{4, 5, 8, 10, 9, 3, 15, 20, 7});
        System.out.println("---------");
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, 0, preorder.length-1, 0, inorder.length -1);
    }

    public TreeNode build(int[] preorder, int[] inorder, int l, int r, int l2, int r2) {
        if (l > r) return null;

        int head = preorder[l];
        int i = 0;
        for (; i < inorder.length; i++) {
            if (head == inorder[i]) break;
        }
        int leftSize = i - l2;
        int rightSzie = r2 - i;
        TreeNode left = build(preorder, inorder, l + 1, l+leftSize, l2, i-1);
        TreeNode right =  build(preorder, inorder, l + leftSize +1, r, i+1, r2);
        TreeNode node = new TreeNode(head);
        node.left = left;
        node.right = right;
        return node;
    }

    public static TreeNode buildTree2(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }



}
